package uestc.lj.basicPromotion.slidingwindow;

import java.util.LinkedList;

/**
 * 求滑动窗口中最大值所组成得到数组
 *
 * @Author:Crazlee
 * @Date:2021/11/26
 */
public class Code01_getmaxValueinWindow {

	public static class Windows {
		private int L;
		private int R;
		private int[] arr;
		private LinkedList<Integer> maxQueue;

		public Windows(int[] arr) {
			this.L = -1;
			this.R = 0;
			this.arr = arr;
			this.maxQueue = new LinkedList<>();
		}

		public void addNumFromRight() {
			if (R == arr.length) {
				return;
			}
			while (!maxQueue.isEmpty() && arr[maxQueue.peekLast()] <= arr[R]) {
				maxQueue.pollLast();
			}
			maxQueue.addLast(R);
			R++;
		}

		public void removeNumFromLeft() {
			if (L >= R - 1) {
				return;
			}
			L++;
			if (maxQueue.peekFirst() == L) {
				maxQueue.pollFirst();
			}
		}

		public Integer getMaxValue() {
			if (!maxQueue.isEmpty()) {
				return arr[maxQueue.peekFirst()];
			}
			return null;
		}
	}


	public static int[] getmaxValueinWindow(int[] array, int window) {
		if (array == null || array.length == 0 || array.length < window) {
			return null;
		}
		//利用双端队列维护窗口的最大值
		LinkedList<Integer> maxQueue = new LinkedList<>();
		int[] result = new int[array.length - window + 1];
		int index = 0;

		for (int i = 0; i < array.length; i++) {
			while (!maxQueue.isEmpty() && maxQueue.peekLast() <= array[i]) {
				maxQueue.pollLast();
			}
			maxQueue.addLast(i);
			//判断过期
			if (maxQueue.peekFirst() == i - window) {
				maxQueue.pollFirst();
			}
			//输出窗口内的最大值
			if (i >= window - 1) {
				result[index++] = array[maxQueue.peekFirst()];
			}
		}
		return result;
	}

	public static void printArray(int[] arr) {
		for (int i = 0; i != arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
		System.out.println();
	}

	public static void main(String[] args) {
		int[] arr = {4, 3, 5, 4, 3, 3, 6, 7};
		int w = 3;
		printArray(getmaxValueinWindow(arr, w));

	}

}
